package number_111;

public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null) {
            return minDepth(root.right) + 1;
        } else if (root.right == null) {
            return minDepth(root.left) + 1;
        } else {
            return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
        }
    }

    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(9);
        TreeNode node1 = new TreeNode(3);
        root.left = node1;
        TreeNode node2 = new TreeNode(10);
        root.right = node2;
        TreeNode node3 = new TreeNode(11);
        node2.left = node3;
        TreeNode node4 = new TreeNode(12);
        node2.right = node4;

        System.out.println(new Solution().minDepth(root));
    }
}
